package zld;

import java.util.Scanner;

public class ZLD {

    public static void main(String[] args) {        
        
        // WCZYTYWANIE
        Scanner in = new Scanner(System.in);
        System.out.print("Podaj wymiar maceirzy: ");
        System.out.print("x: ");
        int x = in.nextInt();
        System.out.print("y: ");
        int y = in.nextInt();
        int[][] tabKosztow = new int[x+1][y+1];
        int[][] tabWybranych = new int[x+1][y+1];
        boolean [][] tabBool = new boolean[x+1][y+1];

        System.out.println("Koszty: ");
        for ( int i=0; i<x; i++)
        {
            for ( int j=0; j<y; j++)
            {
                System.out.print((i+1)+" "+(j+1)+": ");
                tabKosztow[i][j]=in.nextInt();
                tabWybranych[i][j]=0;
                tabBool[i][j]=false;
            }        
        }       

        System.out.println();
        for ( int i=0; i<x; i++)
        {
            for ( int j=0; j<y; j++)
                System.out.print(tabKosztow[i][j]);
            System.out.println();
        }
        int[] tabD = new int[y+1];
        int[] tabO = new int[x+1];
        int[] tabDtemp = new int[y+1];
        int[] tabOtemp = new int[x+1];

        System.out.println("Podaj popyt (Odbiorcy)");
        for ( int i=0; i<x; i++)
        {
            System.out.print((i+1)+": ");
            tabO[i] = in.nextInt();
            tabOtemp[i]=tabO[i];
        }

        System.out.println("Podaj podaż (Dostawcy)");
        for ( int i=0; i<y; i++)
        {
            System.out.print((i+1)+": ");
            tabD[i] = in.nextInt();
            tabDtemp[i]=tabD[i];
        }
        System.out.println();
        
        int min=1000;
        int wspi=0;
        int wspj=0;
        int roznicaOD;

        boolean czyBylo=false;
        
        //WYSZUKANIE MIMIMUM I OBLICZENIA
        do
        {
            czyBylo=false;
            min=1000;
            for ( int i=0; i<x; i++)
            {
                for ( int j=0; j<y; j++)
                {
                    if (tabBool[i][j]==false)
                    {
                        if (tabKosztow[i][j] < min) 
                        {   
                            min = tabKosztow[i][j];
                            wspi= i;
                            wspj = j;
                            czyBylo=true;
                        }
                    }
                }
            }
            roznicaOD = tabOtemp[wspi]-tabDtemp[wspj];
            System.out.println(roznicaOD);
            System.out.println(wspi);
            System.out.println(wspj);
            
            if(roznicaOD<=0 && czyBylo==true) 
            {
                tabWybranych[wspi][wspj]=tabOtemp[wspi];
                tabDtemp[wspj]-=tabOtemp[wspi];
                tabOtemp[wspi]=0;
                for (int j=0;j<y;j++)
                    if (tabBool[wspi][j]==false)
                        tabBool[wspi][j]=true;
            }
            if(roznicaOD>0 && czyBylo==true) 
            {
                tabWybranych[wspi][wspj]=tabOtemp[wspi]-roznicaOD;
                tabDtemp[wspj]=0;
                tabOtemp[wspi]=roznicaOD;
                tabBool[wspi][wspj]=true;
            } 
            
            for ( int i=0; i<x; i++)
            {
                for ( int j=0; j<y; j++)
                    System.out.print(tabWybranych[i][j]+" ");
                System.out.println();
            }
        }while (czyBylo==true);
            
           int K=0;
           for ( int i=0; i<x; i++)
               for ( int j=0; j<y; j++)
                   if(tabWybranych[i][j]!=0) K+=tabWybranych[i][j]*tabKosztow[i][j];
           System.out.println("K: "+K);
            
            
            
        boolean czyUjemne = false;
            // PĘTLA GŁÓWNA!   DO KOŃCA PROGRAMU !! !! !!
        do
        {
            
            //OBLICZENIE K
            
            // OBLICZAM alfa i beta    
            int[] alfaD = new int[y+1];
            int[] betaO = new int[x+1];
            boolean[] alfaDBool = new boolean[y+1];
            boolean[] betaOBool = new boolean[x+1];
            for ( int i=0; i<x; i++)
            {
                betaOBool[i]=false;
            }
            for ( int i=0; i<y; i++)
            {
                alfaDBool[i]=false;
            }
            alfaD[0]=0;
            alfaDBool[0]=true;
            boolean czyWszystkie=false;
            do
            {
                czyWszystkie=true;
                for ( int i=0; i<x; i++)
                    for ( int j=0; j<y; j++)        
                    {
                        if(tabWybranych[i][j]!=0) 
                        { 
                            if(alfaDBool[j]==true && betaOBool[i]==false) 
                            {
                                betaO[i]=tabKosztow[i][j]-alfaD[j];
                                betaOBool[i]=true;
                            }
                            if(alfaDBool[j]==false && betaOBool[i]==true)
                        {
                            alfaD[j]=tabKosztow[i][j]-betaO[i];
                            alfaDBool[j]=true;
                        }
                    }
                }
    
                for ( int i=0; i<x; i++)
                {
                    if(betaOBool[i]==false) czyWszystkie=false;
                }
                for ( int i=0; i<y; i++)
                {
                    if(alfaDBool[i]==false) czyWszystkie=false;
                }                
            
            }while(czyWszystkie==false);
        
             System.out.println();                    
            System.out.println("Alfa:");
            for ( int i=0; i<y; i++)
            {
                System.out.print(alfaD[i]+" ");
            }
            System.out.println();  
            System.out.println("Beta:");
            for ( int i=0; i<x; i++)
            {
                System.out.print(betaO[i]+" ");
            }
            System.out.println();     

            int ileZerWDelta=0;
            int minimumDelta=0;
            //OBLICZENIE DELTA
            int[][] tabDelta = new int[x+1][y+1];
            czyUjemne = false;
            int[][] tabSciezkaDelta = new int[4][2];        //x,y
            for ( int i=0; i<x; i++)
                for ( int j=0; j<y; j++)        
                {
                    tabDelta[i][j]=tabKosztow[i][j]-alfaD[j]-betaO[i];
                    if(tabDelta[i][j]<0) 
                    {
                        czyUjemne=true;
                        if(tabDelta[i][j]<minimumDelta)
                        {
                            minimumDelta=tabDelta[i][j];
                            tabSciezkaDelta[0][0]=i;
                            tabSciezkaDelta[0][1]=j;
                        }
                    }
                    if(tabDelta[i][j]==0)
                        ileZerWDelta++;                        
                }
            System.out.println();  
            System.out.println("Delta:");        
            for ( int i=0; i<x; i++)
            {
                for ( int j=0; j<y; j++)
                    System.out.print(tabDelta[i][j]+" ");
                System.out.println();
            }        
            System.out.println();

            // WYSZUKANIE WSPÓŁRZĘDNYCH XSÓW W DELTA
            int [][] tabWspZerWDelta = new int[ileZerWDelta][2];
            int k=0;
            System.out.println("ileZerWDelta: "+ileZerWDelta);
            for ( int i=0; i<x; i++)
                for ( int j=0; j<y; j++)        
                {
                    if(tabDelta[i][j]==0) 
                    {
                        tabWspZerWDelta[k][0]=i;
                        tabWspZerWDelta[k][1]=j;
                        k++;
                    }
                }

            // OBLICZENIE ŚCIEŻKI PO DELCIE

            if(czyUjemne)
            {
                for ( int i=0; i<ileZerWDelta; i++)
                    for ( int j=0; j<ileZerWDelta; j++)
                        for ( int l=0; l<ileZerWDelta; l++)
                            if(i!=j && j!=l && tabSciezkaDelta[0][1]==tabWspZerWDelta[i][1] && tabSciezkaDelta[0][0]==tabWspZerWDelta[j][0] && tabWspZerWDelta[j][1]==tabWspZerWDelta[l][1] && tabWspZerWDelta[i][0]==tabWspZerWDelta[l][0])
                            {
                                System.out.println("i, l, j");                                
                                System.out.println(tabWspZerWDelta[i][0]);
                                System.out.println(tabWspZerWDelta[i][1]);
                                System.out.println(tabWspZerWDelta[l][0]);
                                System.out.println(tabWspZerWDelta[l][1]);
                                System.out.println(tabWspZerWDelta[j][0]);
                                System.out.println(tabWspZerWDelta[j][1]);
                                    tabSciezkaDelta[1][0]=tabWspZerWDelta[i][0];
                                    tabSciezkaDelta[1][1]=tabWspZerWDelta[i][1];
                                    tabSciezkaDelta[2][0]=tabWspZerWDelta[l][0];
                                    tabSciezkaDelta[2][1]=tabWspZerWDelta[l][1];
                                    tabSciezkaDelta[3][0]=tabWspZerWDelta[j][0];
                                    tabSciezkaDelta[3][1]=tabWspZerWDelta[j][1];                        
 

                                break;
                            }
                    

                System.out.println();  
                System.out.println("Ścieżka minimalizacji:");        
                for ( int i=0; i<4; i++)
                {
                    for ( int j=0; j<2; j++)
                    {
                        System.out.print(tabSciezkaDelta[i][j]+" ");
                    }
                    System.out.println();
                }        
                if (tabSciezkaDelta[3][0]==tabSciezkaDelta[0][0]) 
                    System.out.println("Ścieżka: OK");
                else
                    System.out.println("Ścieżka: BŁĄD!!");                
                System.out.println();


            //OBLICZENIA DELTY PO OPTYMALIZACJI
            if( tabWybranych[ tabSciezkaDelta[1][0] ][ tabSciezkaDelta[1][1] ] <= tabO[tabSciezkaDelta[0][0]] )
                tabWybranych[ tabSciezkaDelta[0][0] ][tabSciezkaDelta[0][1]] = tabWybranych[ tabSciezkaDelta[1][0] ][tabSciezkaDelta[1][1]];
            else
                tabWybranych[ tabSciezkaDelta[0][0] ][tabSciezkaDelta[0][1]] = tabO[tabSciezkaDelta[0][0]];

            tabWybranych[ tabSciezkaDelta[1][0] ][tabSciezkaDelta[1][1]] -= tabWybranych[ tabSciezkaDelta[0][0] ][tabSciezkaDelta[0][1]];

            tabWybranych[ tabSciezkaDelta[3][0] ][tabSciezkaDelta[3][1]] = tabO[tabSciezkaDelta[3][0]] - tabWybranych[ tabSciezkaDelta[0][0] ][tabSciezkaDelta[0][1]];        

            tabWybranych[ tabSciezkaDelta[2][0] ][tabSciezkaDelta[2][1]] += tabWybranych[ tabSciezkaDelta[0][0] ][tabSciezkaDelta[0][1]];

            }


            for ( int i=0; i<x; i++)
            {
                for ( int j=0; j<y; j++)
                    System.out.print(tabWybranych[i][j]+" ");
                System.out.println();
            }
            
            K=0;
            for ( int i=0; i<x; i++)
               for ( int j=0; j<y; j++)
                   if(tabWybranych[i][j]!=0) K+=tabWybranych[i][j]*tabKosztow[i][j];
           System.out.println("K: "+K);
           
        }while(czyUjemne==true);

            System.out.println();
            System.out.println("Koniec programu! Obliczone: ");
            for ( int i=0; i<x; i++)
            {
                for ( int j=0; j<y; j++)
                    System.out.print(tabWybranych[i][j]+" ");
                System.out.println();
            }

            
            
            // DO ZROBIENIA !! !! !! !! !!
            // dorobić fikcyjnych dostawców / odbiorców
    }
}